package com.sheng.leetcode.year2022.month04.day20;

import org.junit.Test;

import java.util.HashMap;
import java.util.Map;

/**
 * @author liusheng
 * @date 2022/04/20
 *
 * 388. 文件的最长绝对路径
 *
 * 假设有一个同时存储文件和目录的文件系统。下图展示了文件系统的一个示例：
 *
 * 这里将 dir 作为根目录中的唯一目录。dir 包含两个子目录 subdir1 和 subdir2 。
 * subdir1 包含文件 file1.ext 和子目录 subsubdir1；
 * subdir2 包含子目录 subsubdir2，该子目录下包含文件 file2.ext 。
 *
 * 在文本格式中，如下所示(⟶表示制表符)：
 *
 * dir
 * ⟶ subdir1
 * ⟶ ⟶ file1.ext
 * ⟶ ⟶ subsubdir1
 * ⟶ subdir2
 * ⟶ ⟶ subsubdir2
 * ⟶ ⟶ ⟶ file2.ext
 *
 * 如果是代码表示，上面的文件系统可以写为 "dir\n\tsubdir1\n\t\tfile1.ext\n\t\tsubsubdir1\n\tsubdir2\n\t\tsubsubdir2\n\t\t\tfile2.ext" 。
 * '\n' 和 '\t' 分别是换行符和制表符。
 *
 * 文件系统中的每个文件和文件夹都有一个唯一的 绝对路径 ，即必须打开才能到达文件/目录所在位置的目录顺序，所有路径用 '/' 连接。
 * 上面例子中，指向 file2.ext 的 绝对路径 是 "dir/subdir2/subsubdir2/file2.ext" 。
 * 每个目录名由字母、数字和/或空格组成，每个文件名遵循 name.extension 的格式，
 * 其中 name 和 extension由字母、数字和/或空格组成。
 *
 * 给定一个以上述格式表示文件系统的字符串 input ，返回文件系统中 指向 文件 的 最长绝对路径 的长度 。 如果系统中没有文件，返回 0。
 *
 * 示例 1：
 *
 * dir
 * ⟶ subdir1
 * ⟶ subdir2
 * ⟶ ⟶ file2.ext
 *
 * 输入：input = "dir\n\tsubdir1\n\tsubdir2\n\t\tfile.ext"
 * 输出：20
 * 解释：只有一个文件，绝对路径为 "dir/subdir2/file.ext" ，路径长度 20
 * 示例 2：
 *
 * dir
 * ⟶ subdir1
 * ⟶ ⟶ file1.ext
 * ⟶ ⟶ subsubdir1
 * ⟶ subdir2
 * ⟶ ⟶ subsubdir2
 * ⟶ ⟶ ⟶ file2.ext
 *
 * 输入：input = "dir\n\tsubdir1\n\t\tfile1.ext\n\t\tsubsubdir1\n\tsubdir2\n\t\tsubsubdir2\n\t\t\tfile2.ext"
 * 输出：32
 * 解释：存在两个文件：
 * "dir/subdir1/file1.ext" ，路径长度 21
 * "dir/subdir2/subsubdir2/file2.ext" ，路径长度 32
 * 返回 32 ，因为这是最长的路径
 * 示例 3：
 *
 * a
 *
 * 输入：input = "a"
 * 输出：0
 * 解释：不存在任何文件
 * 示例 4：
 *
 * ⟶ file1.ext
 * ⟶ file2.ext
 * ⟶ nlongfile.ext
 *
 * 输入：input = "file1.txt\nfile2.txt\nlongfile.txt"
 * 输出：12
 * 解释：根目录下有 3 个文件。
 * 因为根目录中任何东西的绝对路径只是名称本身，所以答案是 "longfile.txt" ，路径长度为 12
 *
 * 提示：
 *
 * 1 <= input.length <= 104
 * input 可能包含小写或大写的英文字母，一个换行符 '\n'，一个制表符 '\t'，一个点 '.'，一个空格 ' '，和数字。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/longest-absolute-file-path
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class LeetCode0388 {

    @Test
    public void test01(){
        //String input = "dir\n\tsubdir1\n\tsubdir2\n\t\tfile.ext";
        String input = "dir\n\tsubdir1\n\t\tfile1.ext\n\t\tsubsubdir1\n\tsubdir2\n\t\tsubsubdir2\n\t\t\tfile2.ext";
        //String input = "a";
        //String input = "file1.txt\nfile2.txt\nlongfile.txt";
        System.out.println(new Solution().lengthLongestPath(input));
    }

}
//class Solution {
//    public int lengthLongestPath(String input) {
//        String s1 = ".";
//        String s2 = "\t";
//        String s3 = "\\n";
//        if (input.indexOf(s1) == -1) {
//            //说明没有文件存在
//            return 0;
//        } else if (input.indexOf(s2) == -1) {
//            //说明没有文件夹存在
//            String[] split = input.split(s3);
//            int max = split[0].length();
//            for (int i = 1; i < split.length; i++) {
//                if (max < split[i].length()) {
//                    max = split[i].length();
//                }
//            }
//            return max;
//        } else {
//            //说明既存在文件，也存在文件夹
//            String[] split = input.split(s3);
//            for (int i = 0; i < split.length; i++) {
//                System.out.println(split[i]);
//            }
//            return 0;
//        }
//    }
//}
class Solution {
    public int lengthLongestPath(String s) {
        //存储每一级文件的绝对路径，key代表层级，value代表绝对路径
        Map<Integer, String> map = new HashMap<>(16);
        //n代表字符串的长度，\t和\n视作一位
        int n = s.length();
        //ans代表绝对路径最长的文件的路径
        String ans = null;
        for (int i = 0; i < n; ) {
            //目录的层级
            int level = 0;
            //一个\t代表一个层级
            while (i < n && s.charAt(i) == '\t' && ++level >= 0) {
                i++;
            }
            //走完上一个while后的i代表\t后一个字符所处的位置，从0开始计算的下标，而level则代表当前文件或文件夹的层级
            int j = i;
            boolean isDir = true;
            //走完当前while后j的位置就是\n所在的位置，从0开始计算的下标
            while (j < n && s.charAt(j) != '\n') {
                //如果判断到当前有.，则代表是文件
                if (s.charAt(j++) == '.') {
                    isDir = false;
                }
            }
            //代表上一个\t到下一个\n之间的字符串，即文件或文件夹的全称
            String cur = s.substring(i, j);
            //代表当前文件夹或文件的上一级目录的路径
            String prev = map.getOrDefault(level - 1, null);
            //当前文件或文件夹的绝对路径
            String path = prev == null ? cur : prev + "/" + cur;
            //判断是否为文件夹
            if (isDir) {
                //是文件夹则，level是文件夹层级，0为根目录，path是文件夹的绝对路径
                map.put(level, path);
            } else if (ans == null || path.length() > ans.length()) {
                //第一个文件直接进行赋值，如果当前文件的绝对路径长度大于上一个文件的绝对路径长度则进行替换
                ans = path;
                //System.out.println(ans);
            }
            //每一次都将j，也就是\n所在的后一位的坐标赋值给i
            i = j + 1;
        }
        //ans==null，则代表全都是文件夹，没有文件，返回0，否则返回长度
        return ans == null ? 0 : ans.length();
    }
}
//
//作者：AC_OIer
//链接：https://leetcode-cn.com/problems/longest-absolute-file-path/solution/by-ac_oier-c55t/
//来源：力扣（LeetCode）
//著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

//class Solution {
//    static int[] hash = new int[10010];
//    public int lengthLongestPath(String s) {
//        //将数组hash的值全部初始化为-1
//        Arrays.fill(hash, -1);
//        //n代表字符串s的长度，ans代表文件绝对路径的长度
//        int n = s.length(), ans = 0;
//        for (int i = 0; i < n; ) {
//            //level代表目录的层级，从0开始
//            int level = 0;
//            //一个\t代表一个层级
//            while (i < n && s.charAt(i) == '\t' && ++level >= 0) {
//                i++;
//            }
//            int j = i;
//            //是否为文件夹
//            boolean isDir = true;
//            while (j < n && s.charAt(j) != '\n') {
//                if (s.charAt(j++) == '.') {
//                    isDir = false;
//                }
//            }
//            //代表当前文件或文件夹的名称的长度
//            Integer cur = j - i;
//            //当前文件或文件夹上一级目录的长度
//            Integer prev = level - 1 >= 0 ? hash[level - 1] : -1;
//            Integer path = prev + 1 + cur;
//            if (isDir) {
//                //将当前文件的路径存放
//                hash[level] = path;
//            } else if (path > ans) {
//                ans = path;
//            }
//            i = j + 1;
//        }
//        return ans;
//    }
//}
//
//作者：AC_OIer
//链接：https://leetcode-cn.com/problems/longest-absolute-file-path/solution/by-ac_oier-c55t/
//来源：力扣（LeetCode）
//著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
